1. Field of the Invention
This invention relates to the field of computer software, and, more specifically, to transaction processing and object or resource locking.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever. Sun, Sun Microsystems, the Sun logo, Solaris, Java, JavaOS, JavaStation, HotJava Views and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.
2. Background Art
In modern computing environments, it is commonplace to store and access a variety of diverse information and data. To efficiently utilize the information, the information is stored in a database and is structured in a manner that provides a user with the ability to interpret and manipulate the information (referred to as a "data structure"). One type of database structure is in the form of a table, where each row of the table contains a record and each column specifies a field in the record. For example, a table can be used to store information regarding a company's inventory where each record is a specific item in the inventory and each field specifies information about the item (e.g., the name of the product, the price of the product, etc.). Data structures may vary depending on the application and type of database utilized. As a result of the diverse types of information being utilized (e.g., text, images, sound, video, etc.), data structures have grown increasingly complex.
Each time a computer system performs an activity, the activity is referred to as a transaction. For example, when a customer order is entered, or an inventory item is updated, a transaction for each activity is executed by the computer system. Thus, when information in a data structure is accessed or manipulated, a transaction is executed by the computer system. A transaction may need access to a record in a database or a portion of information in a database. Alternatively, a transaction may modify the entire database. When executing transactions, a computer system may execute a group of transactions at one time (referred to as batch processing), or may execute each transaction immediately after the transaction is received by the system (referred to as transaction processing). Transactions contain certain properties that must be adhered to. For example, transactions must be isolated such that each transaction must be contained separately from each other transaction. Additionally, transactions must provide for recoverability (the ability to establish a previous or new status from which execution can be resumed in the event of a system or execution failure ). Required transaction properties are also referred to as low level details of a transaction.
In many modem applications, increasingly complex data structures coupled with transaction processing capabilities is becoming a common requirement. The complexity of these applications, in terms of the data structures, algorithms, and type of the transactions used, does not fit well in the framework offered by traditional database systems. Persistent programming languages (PPL) (programming languages that provide for data to have a lifetime that persists for a specified amount of time) that support transaction processing may be utilized by programmers as an alternative or in combination with traditional database systems. To provide adequate support, some PPLs automatically enforce required transaction properties. Thus, low level transaction details (e.g., enforcing a transaction's properties) are automatically performed without input from a programmer.
One automated low level detail consists of the acquisition and release of a lock. A lock is a mechanism that restricts use of a resource to the holder of the lock. By locking a resource, the integrity of the data in the resource is ensured by preventing more than one user (or transaction) from accessing or changing the same data or object at the same time. There are several types of locks that may be used.
One type of lock is a shared lock. A shared lock permits multiple transactions to read (view) an item simultaneously without any modification or addition to the item (no writing is permitted). A shared lock is referred to as permitting concurrent (or concurrency) control by a transaction (i.e., multiple transactions are permitted to concurrently access a resource). Another type of lock is an exclusive lock. An exclusive lock permits one transaction to read and write to an item while excluding all other transactions from reading or writing to the item.
The locking and unlocking of resources must be administered to ensure that any required lock properties are complied with. For example, two or more different transactions cannot each acquire an exclusive lock at the same time for the same resource. Additionally, locks must be administered to provide a queue for transactions that are waiting to acquire a lock, and to rollback any executed actions if a deadlock results (i.e., when each of two transactions are waiting for a lock release from the other before continuing). For example, a deadlock occurs if transaction 1 has a lock on resource A and is waiting to acquire a lock on resource B, and transaction 2 has a lock on resource B and is waiting to acquire a lock on resource A.
A locking protocol partially determines the administration of a locking and unlocking of resources. A locking protocol determines how and when a transaction is granted (or acquires) a lock for a resource and when the resource is unlocked (i.e., the lock is released allowing other transactions to acquire a lock on that resource). A lock manager administers a locking protocol.
For example, in a two-phase locking protocol, each transaction issues a lock and unlock request in two phases. In one phase, referred to as the growing phase, a transaction may obtain locks but may not release any lock. In the second phase, referred to as the shrinking phase, a transaction may release locks but may not obtain any new locks.
Another protocol, referred to as a graph-based protocol, a partial ordering of information in a database is performed. For example, a set R of resources consisting of R.sub.1, R.sub.2, R.sub.3, . . . , R.sub.h is ordered such that R.sub.i.fwdarw.R.sub.j. In this manner, any transaction accessing both R.sub.i and R.sub.j must access R.sub.i before accessing R.sub.j. With this ordering, the set R may be viewed as a directed acyclic graph, called a database or resource graph. A directed graph may be viewed as the tree of FIG. 2, where each node of the tree is a resource. Each resource descends from another resource (referred to as a parent resource) up to the root of the tree that has no parents (resource A 200). In a graph-based protocol, the following rules are followed: (1) the first lock by a transaction T may be on any data item, (2) subsequently, a data item or resource R can be locked by T only if the parent of R is currently locked by T, (3) resources can be unlocked at any time, and (4) a resource that has been locked and unlocked by T cannot subsequently be relocked by T. For example, referring to FIG. 2, if T needs access to resource C 204, both resource C 204 and resource A 200 must be locked. Similarly, if T needs access to resource J 218, in addition to locking resource J 218, all of the parents of resource J 218 must be locked (i.e., resources H 214, D 208, B 202, and A 200). Thus, in some cases, a transaction must lock resources that it does not access (i.e., the parent resources of a resource being accessed).
FIG. 3 demonstrates an example of lock acquisition according to a traditional protocol. In the traditional protocol, each resource is allocated a lock data structure. This lock data structure is updated every time a lock operation changes the state of the resource's lock. FIG. 3 demonstrates a scenario where two resources, O.sub.1 300 and O.sub.2 302, have been read by a transaction T.sub.1, and O.sub.2 302 is about to be read by transaction T.sub.2. The state of the lock of each resource is shown before (304-306) and after (308-310) the acquisition of the lock on O.sub.2 302 by T.sub.2. When transaction T.sub.2 requests the lock on resource O.sub.2 302 in read mode, the lock data structure associated with O.sub.2 302 is updated to reflect the new lock state (i.e., lock owned by T.sub.1 and T.sub.2 in read mode).
Each of the lockable resources may be a record in a database, a field of a record, an entire database, or in an object oriented system (discussed in detail below) a single object, for example. The size or level of the lockable resource is referred to as the granularity of the resource (e.g., the field level v. the record level v. the table level).
A lock is comprised of a data structure that records the identity of the transactions that are given the right to execute operations on the resource the lock protects. Each time a lock is acquired, memory is used for the lock data structure. The memory utilized by the lock remains unavailable until released through garbage collection or some other method. Consequently, one goal in lock administration is to minimize the memory locks consume, which usually translates in minimizing the number of locks.
The process of creating and manipulating a lock is time consuming. Thus, another goal in lock processing is to minimize the lock processing cost for acquiring and releasing a lock.
As resource granularity becomes finer, more resources are available for transactions. Such resource availability occurs because locks are placed on smaller resource units, freeing remaining resources that may be locked if the resource is coarser. Consequently, another objective in lock processing is to utilize a fine resource granularity.
Locking may be performed manually by programmers who then explicitly put lock requests in their programs, or automatically at runtime without input from programmers. When applied in the context of general purpose programing languages, both solutions may result in many unnecessary redundant lock requests (i.e., a lock request for a lock already owned) because of the complex data structures and algorithms these programming languages enable. Consequently, one goal of lock management is to minimize the processing time spent to process redundant lock requests.
The objective of a lock management implementation is to obtain the best combination of low memory consumption, low processing costs, and fine granularity of locking.